package leetcode;

/**
 * 最大子序和
 * 给定一个整数数组 nums , 找到一个具有最大和的连续子数组（子数组最少包含一个元素）, 返回其最大和
 * 算法 : 动态规划
 *   创建一个 dp 数组 , 记录前 i 个数中的连续最大值
 *   dp[i] = Max(dp[i - 1], dp[i - 1] + nums[i])
 */
public class _53 {
    public static void main(String[] args) {
        System.out.println(new _53().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }

    public int maxSubArray(int[] nums) {
        int ans = 0;
        int[] dp = new int[nums.length];
        ans = dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    // 使用滚动数组，就是数组降维，减少空间的消耗
    public int maxSubArray_perfect(int[] nums) {
//        int[] dp = new int[nums.length];
        int pre = 0, ans = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) pre = nums[i];
            else pre = Math.max(pre + nums[i], nums[i]);
            ans = Math.max(ans, pre);
        }
        return ans;
    }
}
